package alo.p19;

/**
 * @ClassName SubsetHalfSum
 * @Description 数组之和为K，求数组之和为K/2的子集
 * @Author Fanxc
 * @DATE 2021/3/15 20:06
 * @Version 1.0
 */
public class SubsetHalfSum {
    int[] T=new int[100];
    int subsetHalfSum(int[] A,int n){
        int K=0;
        for (int i = 0; i < n; i++) {
            K+=A[i];
        }
        T[0]=1;
        for (int i = 1; i <= K; i++) {
            T[i]=0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = K-A[i]; j >=0 ; j--) {
                if (T[j]==1){
                    T[j+A[i]]=1;
                }
            }
        }
        return T[K/2];
    }
}
